namespace Algorithm.LeetCode
{
    /// <summary>
    /// 第二十一题：合并两个有序链表
    /// </summary>
    public class No21
    {
        /*
         * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
         *
         * 输入：l1 = [1,2,4], l2 = [1,3,4]
         * 输出：[1,1,2,3,4,4]
         */
        public static ListNode MergeTwoLists(ListNode l1, ListNode l2)
        {
            if (l1 == default)
            {
                return l2;
            }

            if (l2 == default)
            {
                return l1;
            }

            var resultListNode = l1.val < l2.val ? l1 : l2;
            resultListNode.next = MergeTwoLists(resultListNode.next, l1.val >= l2.val ? l1 : l2);

            return resultListNode;
        }

        public class ListNode
        {
            public int val { get; set; }
            public ListNode next { get; set; }

            public ListNode(int val = 0, ListNode next = null)
            {
                this.val = val;
                this.next = next;
            }

            public static bool Compare(ListNode node1, ListNode node2)
            {
                if (node1 == default)
                {
                    return node2 == default;
                }

                return node1.val == node2.val && Compare(node1.next, node2.next);
            }
        }
    }
}